#include <stdio.h>
#include <stdlib.h>
#include <cctype>
#include <string>
#include <iostream>
#include <vector>

// Type Declarations

enum PrintBehavior {
    CloseAtSameLine,
    CloseAtOtherLine
};

typedef std::string Symbol;
typedef std::vector<Symbol> SymTab;
typedef SymTab* TabPtr;

/* Variable Declarations */
char        Look;               // Lookahead Character
char        Token;              // Encoded Token
Symbol      Value;              // Unencoded Token
SymTab      ST;
std::string SType;
int         LCount  = 0;        // Label Count
const int   buf_len = 64;
int         DLevel  = 0;        // Debug log level

// Definition of Keywords and Token Types
SymTab KWlist{
    "IF", "ELSE", "ENDIF", "WHILE", "ENDWHILE",
        "READ", "WRITE", "VAR", "END"};

// The 'x' in KWcode identify error(or to say, not keyword) 
std::string KWcode("xileweRWve");


// Forward Declaration
void Next();
void GetName();
void Store(const Symbol& Name);
void Undefined(const std::string& n);
void Duplicate(const std::string& n);


// Table Lookup

// If the input string matches a table entry, return the entry index.
// If not, return a -1.

int Lookup(const TabPtr T, const Symbol& s) {
    for (int i = 0; i < T->size(); ++i) {
        if (s == (*T)[i]) {
            return i;
        }
    }
    return -1;
}

// Locate a Symbol in Symbol Table.
// Returns the index of the entry. -1 if not present.
int Locate(const Symbol& N) {
    return Lookup(&KWlist, N);
}

// Look for Symbol in Table
bool InTable(const Symbol& n) {
    return (Lookup(&ST, n) != -1);
}

// Check to See if an Identifier is in the Symbol Table
// Report an error if it's not.
void CheckTable(const Symbol& N) {
    if (!InTable(N)) {
        Undefined(N);
    }
}

// Check the Symbol Table for a Duplicate Identifier.
// Report an error if Identifier is already in table.
void CheckDup(const Symbol& N) {
    if (InTable(N)) {
        Duplicate(N);
    }
}



// Get an Identifier and Scan it for Keywords
void Scan() {
    if (Token == 'x') {
        Token = KWcode[Lookup(&KWlist, Value) + 1];
    }
}

/* Print Token. Usage: PrintEnter(Token, CloseAtOtherLine/CloseAtSameLine).
   If CloseAtOtherLine, when going out of the Token name scope, you must call PrintLeave().
*/
void PrintEnter(const char* s, PrintBehavior behavior = CloseAtOtherLine) {
    for (int i = 0; i < DLevel; ++i) {
        printf("\t");
    }
    printf("<%s", s);
    if (behavior == CloseAtSameLine) {
        printf(">\n");
    }
    else {
        printf("\n");
        ++DLevel;
    }
}

void PrintLeave() {
    for (int i = 1; i < DLevel; ++i) {
        printf("\t", DLevel);
    }
    printf(">\n");
    --DLevel;
}

/* Report an Error */
template<typename T>
void WriteLn(const T& t) {
    std::cout << t << std::endl;
}

void Error(const std::string& s) {
    std::cout << std::endl;
    std::cout << "Error: " << s << "." << std::endl;
}

/* Report Error and Halt */
void Abort(const std::string& s) {
    Error(s);
    exit(0);
}

/* Report What Was Expected */
void Expected(const std::string& s) {
    Abort(s + " Expected");
}

// Report an Undefined Identifier
void Undefined(const std::string& n) {
    Abort("Undefined Identifier " + n);
}

// Report a Duplicate Identifier
void Duplicate(const std::string& n) {
    Abort("Duplicate Identifier " + n);
}

// Check to Make Sure the Current Token is an Identifier
void CheckIdent() {
    if (Token != 'x') {
        Expected("Identifier");
    }
}

/* Output a String with Tab */
void EmitLn(const std::string& s) {
    std::cout << "\t " << s << std::endl;
}

// Clear the Primary Register
void Clear() {
    EmitLn("CLR D0");
}

// Negate the Primary Register
void Negate() {
    EmitLn("NEG D0");
}

// Load a Constant Value to Primary Register
void LoadConst(const std::string& n) {
    std::cout << "\t MOVE #";
    std::cout << n << ",D0" << std::endl;
}

// Load a Variable to Primary Register
void LoadVar(const Symbol& Name) {
    if (!InTable(Name)) {
        Undefined(Name);
    }
    EmitLn(std::string("MOVE ") + Name + "(PC),D0");
}

// Read Variable to Primary Register
void ReadIt(const std::string& Name) {
    EmitLn("BSR READ");
    Store(Name);
}

// Write Variable from Primary Register
void WriteIt() {
    EmitLn("BSR WRITE");
}

// Push Primary onto Stack
void Push() {
    EmitLn("MOVE D0,-(SP)");
}

// Add Top of Stack to Primary
void PopAdd() {
    EmitLn("ADD (SP)+,D0");
}

// Subtract Primary from Top of Stack
void PopSub() {
    EmitLn("SUB (SP)+,D0");
    EmitLn("NEG D0");
}

// Multiply Top of Stack by Primary
void PopMul() {
    EmitLn("MULS (SP)+,D0");
}

// Divide Top of Stack by Primary
void PopDiv() {
    EmitLn("MOVE (SP)+,D7");
    EmitLn("EXT.L D7");
    EmitLn("DIVS D0,D7");
    EmitLn("MOVE D7,D0");
}

// Store Primary to Variable
void Store(const Symbol& Name) {
    if (!InTable(Name)) {
        Undefined(Name);
    }
    EmitLn(std::string("LEA ") + Name + "(PC),A0");
    EmitLn("MOVE D0,(A0)");
}

/* Read New Character From Input Stream */
void GetChar() {
    Look = getchar();
}

// Generate a Unique Label
std::string NewLabel() {
    char buf[buf_len] = {0};
    sprintf(buf, "L%d", LCount);
    LCount++;

    return buf;
}

// Post a Label To Output
void PostLabel(const std::string& L) {
    WriteLn(L + ":");
}

/* Recognize White Space */
int IsWhite(char c) {
    if (c==' ' ||
        c=='\t' ||
        c=='\r' ||
        c=='\n') {
        return 1;
    }
    else {
        return 0;
    }
    // return isspace(c);
}

/* Skip Over Leading White Space */
void SkipWhite() {
    while (IsWhite(Look)) {
        GetChar();
    }
}

// Skip Over a Comma
void SkipComma() {
    SkipWhite();
    if (Look == ',') {
        GetChar();
        SkipWhite();
    }
}

// Skip a CRLF
void Fin() {
    while ((Look == '\n') || (Look == '\r')) {
        GetChar();
    }
    SkipWhite();
}

// Skip Over an End-of-Line
void NewLine() {
    Fin();
}

/* Match a Specific Input Character */
void Match(char x) {
    if (Look == x) {
        GetChar();
        SkipWhite();
    }
    else {
        char buf[buf_len] = {0};
        sprintf(buf, "'''' %c ''''", x);
        Expected(buf);
    }
}

// Match a Specific Input String
void MatchString(const std::string& x) {
    if (Value != x) {
        WriteLn("Value is: " + Value);
        Expected("''''" + x + "''''");
    }
    Next();
}

// Match a Semicolon
void Semi() {
    if (Token == ';') {
        Next();
    }
}

/* Recognize an Alpha Character  */
int IsAlpha(char c) {
    return isalpha(c);
}

/* Recognize a Decimal Digit */
int IsDigit(char c) {
    return isdigit(c);
}

/* Recognize an Alphanumeric Character */
int IsAlNum(char c) {
    return (IsAlpha(c) || IsDigit(c));
}

/* Recognize an Addop */
int IsAddop(char c) {
    if ((c == '+') ||
        (c == '-')) {
        return 1;
    }
    else {
        return 0;
    }
}

// Recognize a Mulop
int IsMulop(char c) {
    if ((c == '*') ||
        (c == '/')) {
        return 1;
    }
    else {
        return 0;
    }
}

// Recognize a Boolean Orop
bool IsOrOp(char c) {
    if (c == '|' ||
        c == '~') {
        return true;
    }
    else {
        return false;
    }
}

/* Get an Identifier */
void GetName() {
    SkipWhite();
    if (!IsAlpha(Look)) {
        Expected("Name");
    }

    Token = 'x';
    Value = "";
    do {
        Value += toupper(Look);
        GetChar();
    } while (IsAlNum(Look));
}

/* Get a Number */
void GetNum() {
    SkipWhite();
    if (!IsDigit(Look)) {
        Expected("Integer");
    }

    Token = '#';
    Value = "";
    do {
        Value += Look;
        GetChar();
    } while (IsDigit(Look));
}

// Get a Operator
void GetOp() {
    SkipWhite();
    Token = Look;
    Value = Look;
    GetChar();
}

// Get the Next Input Token
void Next() {
    SkipWhite();

    if (IsAlpha(Look)) {
        GetName();
    }
    else if (IsDigit(Look)) {
        GetNum();
    }
    else {
        GetOp();
    }
}

// Add a New Entry to Symbol Table. N is variable name, T is TokenType.
void AddEntry(const Symbol& N, char T) {
    CheckDup(N);
    ST.push_back(N);
    SType.push_back(T);
}

// Allocate Storage for a Static Variable
void Allocate(const Symbol& Name, const std::string& Val) {
    WriteLn(Name + ":\tDC " + Val);
}

// Allocate Storage for a Variable
void Alloc() {
    Next();
    if (Token != 'x') {
        Expected("Variable Name");
    }
    CheckDup(Value);
    AddEntry(Value, 'v');
    Allocate(Value, "0");
    Next();
}

// Write Header Info REQUIRED by Assembler
void Header() {
    WriteLn("WARMST\tEQU $A01E");
    EmitLn("LIB TINYLIB");
}

// Write the Prolog
void Prolog() {
    PostLabel("MAIN");
}

// Write the Epilog
void Epilog() {
    EmitLn("DC WARMST");
    EmitLn("END MAIN");
}

// Parse and Translate Global Declarations
void TopDecls() {
    Scan();
    while (Token == 'v') {
        Alloc();
        while (Token == ',') {
            Alloc();
        }
        Semi();
    }
}

// Forward declaration
void Block();
void Expression();
void BoolExpression();
void NextExpression();
void CompareExpression();

// Parse and Translate a Math Factor
void Factor() {
    if (Token == '(') {
        Next();
        BoolExpression();
        MatchString(")");
    }
    else {
        if (Token == 'x') {
            LoadVar(Value);
        }
        else if (Token == '#') {
            LoadConst(Value);
        }
        else {
            Expected("Math Factor");
        }

        Next();
    }
}

// Recognize and Translate a Multiply
void Multiply() {
    Next();
    Factor();
    PopMul();
}

// Recognize and Translate a Divide
void Divide() {
    Next();
    Factor();
    PopDiv();
}

// Parse and Translate a Math Term
void Term() {
    Factor();
    while (IsMulop(Token)) {
        Push();
        if (Token == '*') {
            Multiply();
        }
        else if (Token == '/') {
            Divide();
        }
        else {
            Abort("Must be Mulop");
        }
    }
}

// Recognize and Translate an Add
void Add() {
    Next();
    Term();
    PopAdd();
}

// Recognize and Translate a Subtract
void Subtract() {
    Next();
    Term();
    PopSub();
}

// Recognize a Relop
bool IsRelop(char c) {
    if (c == '=' ||
        c == '#' ||
        c == '<' ||
        c == '>') {
        return true;
    }
    else {
        return false;
    }
}

// Complement the Primary Register
void NotIt() {
    EmitLn("NOT D0");
}

// AND Top of Stack with Primary
void PopAnd() {
    EmitLn("AND (SP)+,D0");
}

// OR Top of Stack with Primary
void PopOr() {
    EmitLn("OR (SP)+,D0");
}

// XOR Top of Stack with Primary
void PopXor() {
    EmitLn("EOR (SP)+,D0");
}

// Compare Top of Stack with Primary
void PopCompare() {
    EmitLn("CMP (SP)+,D0");
}

// Set D0 If Compare was =
void SetEqual() {
    EmitLn("SEQ D0");
    EmitLn("EXT D0");
}

// Set D0 If Compare was !=
void SetNEqual() {
    EmitLn("SNE D0");
    EmitLn("EXT D0");
}

// Set D0 If Compare was >
void SetGreater() {
    EmitLn("SGT D0");
    EmitLn("EXT D0");
}

// Set D0 If Compare was <
void SetLess() {
    EmitLn("SLT D0");
    EmitLn("EXT D0");
}

// Set D0 If Compare was <=
void SetLessOrEqual() {
    EmitLn("SGE D0");
    EmitLn("EXT D0");
}

// Set D0 If Compare was >=
void SetGreaterOrEqual() {
    EmitLn("SLE D0");
    EmitLn("EXT D0");
}

// Recognize and Translate a Relational "Equals"
void Equals() {
    NextExpression();
    SetEqual();
}

// Recognize and Translate a Relational "Not Equals"
void NotEquals() {
    NextExpression();
    SetNEqual();
}

// Recognize and Translate a Relational "Less Than or Equal"
void LessOrEqual() {
    NextExpression();
    SetLessOrEqual();
}

// Recognize and Translate a Relational "Greater Than or Equal"
void GreaterOrEqual() {
    NextExpression();
    SetGreaterOrEqual();
}

// Recognize and Translate a Relational "Less Than"
void Less() {
    Next();
    if (Token == '=') {
        LessOrEqual();
    }
    else if (Token == '>') {
        NotEquals();
    }
    else {
        CompareExpression();
        SetLess();
    }
}

// Recognize and Translate a Relational "Greater Than"
void Greater() {
    Next();
    if (Token == '=') {
        GreaterOrEqual();
    }
    else {
        CompareExpression();
        SetGreater();
    }
}

// Parse and Translate a Relation
void Relation() {
    Expression();
    if (IsRelop(Token)) {
        Push();
        if (Token == '=') {
            Equals();
        }
        else if (Token == '<') {
            Less();
        }
        else if (Token == '>') {
            Greater();
        }
    }
}

// Parse and Translate a Boolean Factor with Leading NOT
void NotFactor() {
    if (Token == '!') {
        Next();
        Relation();
        NotIt();
    }
    else {
        Relation();
    }
}

// Parse and Translate a Boolean Term
void BoolTerm() {
    NotFactor();
    while (Token == '&') {
        Push();
        Next();
        NotFactor();
        PopAnd();
    }
}

// Recognize and Translate a Boolean OR
void BoolOr() {
    Next();
    BoolTerm();
    PopOr();
}

// Recognize and Translate an Exclusive Or
void BoolXor() {
    Next();
    BoolTerm();
    PopXor();
}

// Parse and Translate a Boolean Expression
void BoolExpression() {
    BoolTerm();
    while (IsOrOp(Token)) {
        Push();
        if (Token == '|') {
            BoolOr();
        }
        else if (Token == '~') {
            BoolXor();
        }
    }
}
    
// Parse and Translate an Expression
void Expression() {
    if (IsAddop(Token)) {
        Clear();
    }
    else {
        Term();
    }
    
    while (IsAddop(Token)) {
        Push();
        if (Token == '+') {
            Add();
        }
        else if (Token == '-') {
            Subtract();
        }
        else {
            Abort("Must be Addop");
        }
    }
}
    
// Get Another Expression and Compare
void CompareExpression() {
    Expression();
    PopCompare();
}

// Get The Next Expression and Compare
void NextExpression() {
    Next();
    CompareExpression();
}
    
// Branch Unconditional
void Branch(const std::string& L) {
    EmitLn("BRA " + L);
}

// Branch False
void BranchFalse(const std::string& L) {
    EmitLn("TST D0");
    EmitLn("BEQ " + L);
}

// Recognize and Translate an IF Construct
void DoIf() {
    std::string L1, L2;
    Next();
    BoolExpression();
    L1 = NewLabel();
    L2 = L1;
    BranchFalse(L1);
    Block();
    if (Token == 'l') {
        Next();
        L2 = NewLabel();
        Branch(L2);
        PostLabel(L1);
        Block();
    }
    PostLabel(L2);
    MatchString("ENDIF");
}

// Parse and Translate a WHILE Statement
void DoWhile() {
    std::string L1, L2;
    Next();
    L1 = NewLabel();
    L2 = NewLabel();
    PostLabel(L1);
    BoolExpression();
    BranchFalse(L2);
    Block();
    MatchString("ENDWHILE");
    Branch(L1);
    PostLabel(L2);
}

// Read a Single Variable
void ReadVar() {
    CheckIdent();
    CheckTable(Value);
    ReadIt(Value);
    Next();
}

// Process a Read Statement
void DoRead() {
    Next();
    MatchString("(");
    ReadVar();
    while (Token == ',') {
        Next();
        ReadVar();
    }
    MatchString(")");
}

// Process a Write Statement
void DoWrite() {
    Next();
    MatchString("(");
    Expression();
    WriteIt();
    while (Token == ',') {
        Next();
        Expression();
        WriteIt();
    }
    MatchString(")");
}

// Parse and Translate an Assignment Statement
void Assignment() {
    std::string Name;
    CheckTable(Value);
    Name = Value;
    Next();
    MatchString("=");
    BoolExpression();
    Store(Name);
}

// Parse and Translate a Block of Statements
void Block() {
    
    Scan();
    while (Token != 'e' && Token != 'l') {
        if (Token == 'i') {
            DoIf();
        }
        else if (Token == 'w') {
            DoWhile();
        }
        else if (Token == 'R') {
            DoRead();
        }
        else if (Token == 'W') {
            DoWrite();
        }
        else if (Token == 'x') {
            Assignment();
        }

        Semi();
        Scan();
    }
}

/* Initialize */
void Init() {
    GetChar();
    Next();
}

/* Main Program */
int main(int argc, char** argv) {
    Init();
    MatchString("PROGRAM");
    Semi();
    Header();
    TopDecls();
    MatchString("BEGIN");
    Prolog();
    Block();
    MatchString("END");
    Epilog();
    return 0;
}
